package com.fang.algorithm.zuo.sort;

import java.util.Arrays;

/**
 * @author lingxiao.fang
 * @Desc todo
 * @createTime 2025/2/11 09:31
 */
public class Test07_QuickSort {
    public static void main(String[] args) {
        int[] arr = {9, 8, 7, 6, 5, 4, 3, 2, 1};
        quickSortTest(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    private static void quickSortTest(int[] arr, int L, int R) {
        if (arr == null || arr.length < 2) {
            return;
        }
        quickProcess(arr, L, R);
    }

    private static void quickProcess(int[] arr, int L, int R) {
        if (L >= R) {
            return;
        }
        int randomIndex = L + (int) (Math.random() * (R - L + 1));
        swap(arr, randomIndex, R);
        int[] partition = quickPartition(arr, L, R);
        quickProcess(arr, L, partition[0] - 1);
        quickProcess(arr, partition[1] + 1, R);
    }

    private static int[] quickPartition(int[] arr, int L, int R) {
        if (L > R) {
            return new int[]{-1, -1};
        }
        if (L == R) {
            return new int[]{L, R};
        }
        int less = L - 1;
        int more = R;
        int index = L;
        while (index < more) {
            if (arr[index] == arr[R]) {
                index++;
            } else if (arr[index] < arr[R]) {
                swap(arr, index, less + 1);
                index++;
                less++;
            } else {
                swap(arr, index, more - 1);
                more--;
            }
        }
        swap(arr, more, R);
        return new int[]{less + 1, more};
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
